package nowcoder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author wangxi created on 2021/6/3 00:23
 * @version v1.0
 *
 * 题目来自于nowcoder 标题：字典树的实现
 *
 * 字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，
 * 请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，
 * 可重复添加；void delete(String word)：删除word，
 * 如果word添加过多次，仅删除一次；
 * boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
 * int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。
 * 现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。
 * 每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，
 * 则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，
 * op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。
 *
 * 对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；
 * 如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。
 */
public class TrieU {

    public static void main(String[] args) {
        String[][] operators = {{"1","qwer"},{"1","qwe"},{"3","qwer"},{"4","q"},{"2","qwer"},{"3","qwer"},{"4","q"}};

        TrieU obj = new TrieU();

        String[] strings = obj.trieU(operators);

        System.out.println(Arrays.toString(strings));
    }


    /**
     *
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    Node root = null;
    public String[] trieU (String[][] operators) {
        // write code here
        if (operators == null || operators.length <= 0 || operators[0].length <= 0) {
            return new String[0];
        }
        List<String> list = new ArrayList<>();
        root = new Node('1');
        for (int i = 0; i < operators.length; i++) {
            if ("1".equals(operators[i][0])) {
                insert(operators[i][1]);
            } else if ("2".equals(operators[i][0])) {
                delete(operators[i][1]);
            } else if ("3".equals(operators[i][0])) {
                boolean searchRes = search(operators[i][1]);
                if (searchRes) {
                    list.add("YES");
                } else {
                    list.add("NO");
                }
            } else if ("4".equals(operators[i][0])) {
                int num = prefixNumber(operators[i][1]);
                // 单词别写错了
                list.add(num + "");
            }
        }
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public static class Node {
        char val;
        boolean isWord;
        Node[] children;
        int count;

        public Node(char val) {
            this.val = val;
            isWord = false;
            children = new Node[26];
            count = 0;
        }
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new Node(c);
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
        node.count++;
    }

    public void delete(String word) {
        // 如果没没有这个word就return了
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                return;
            }
            node = node.children[c - 'a'];
        }
        node.count = 0;
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return node.isWord && node.count != 0;
    }

    int number = 0;
    public int prefixNumber(String pre) {
        Node node = root;
        for (int i = 0; i < pre.length(); i++) {
            char c = pre.charAt(i);
            if (node.children[c - 'a'] == null) {
                return 0;
            }
            node = node.children[c - 'a'];
        }

        // 这里需要重置一下，否则第二次调用就会累加上次的结果
        number = 0;
        dfs(node);
        return number;
    }

    private void dfs(Node node) {
        if (node == null) {
            return;
        }
        number += node.count;
        if (node.children == null || node.children.length <= 0) {
            return;
        }
        for (Node item : node.children) {
            dfs(item);
        }
    }
}
